#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
 
template <class V, class W, W MAX_W = INT_MAX, bool Direction = false>
 
class Graph
{
 
public:
    typedef Graph<V, W, MAX_W, Direction> Self;
    Graph() = default;
    Graph(const V *vertexs, size_t n)
    {
        // reverse 只是预留了，没有做填充。resize() 是做了填充的，默认是用0 做了填充，
        _vertexs.reserve(n);
        for (size_t i = 0; i < n; i++)
        {
            _vertexs.push_back(vertexs[i]);
            _vIndexMap[_vertexs[i]] = i;
        }
        //将MAX_W 作为一个边部存在 的标示值
        _matrix.resize(n);
        for (auto &e : _matrix)
        {
            e.resize(n, MAX_W);
        }
    }
 
    //输入顶点获取顶点的边的数量
    size_t GetVertexIndex(const V &v)
    {
        auto ret = _vIndexMap.find(v);
        if (ret != _vIndexMap.end())
        {
            return ret->second;
        }
        else
        {
            throw invalid_argument("不存在顶点");
            return -1;
        }
    }
 
    void _AddEdge(size_t srci, size_t dsti, const W &w)
    {
 
        _matrix[srci][dsti] = w;
        if (Direction == false)
        {
            _matrix[dsti][srci] = w;
        }
    }
 
    void AddEdge(const V &src, const V &dst, const W &w)
    {
        size_t srci = GetVertexIndex(src);
        size_t dsti = GetVertexIndex(dst);
        _AddEdge(srci, dsti, w);
    }
 
    void Print()
    {
        // 打印顶点和下标映射关系
        for (size_t i = 0; i < _vertexs.size(); ++i)
        {
            cout << _vertexs[i] << "-" << i << " ";
        }
        cout << endl
             << endl;
        cout << " ";
        for (size_t i = 0; i < _vertexs.size(); ++i)
        {
            cout << i << " ";
        }
        cout << endl;
        // 打印矩阵
        for (size_t i = 0; i < _matrix.size(); ++i)
        {
            cout << i << " ";
            for (size_t j = 0; j < _matrix[i].size(); ++j)
            {
                if (_matrix[i][j] != MAX_W)
                    cout << _matrix[i][j] << " ";
                else
                    cout << "#"
                         << " ";
            }
            cout << endl;
        }
        cout << endl
             << endl;
        // 打印所有的边
        for (size_t i = 0; i < _matrix.size(); ++i)
        {
            for (size_t j = 0; j < _matrix[i].size(); ++j)
            {
                if (i < j && _matrix[i][j] != MAX_W)
                {
                    cout << _vertexs[i] << "-" << _vertexs[j] << ":" << _matrix[i][j] << endl;
                }
            }
        }
    }
 
    void Bfs(const V &src)
    {
 
        size_t srcindex = GetVertexIndex(src);
        vector<bool> visited(_matrix.size(), false);
        size_t n = _matrix.size();
        queue<size_t> q;
        q.push(srcindex);
 
        visited[srcindex] = true;
        size_t d = 1;
        size_t dSize = 1;
 
        while (!q.empty())
        {
 
            printf("%s degree%d", src.c_str(), d);
 
            while (dSize--)
            {
                size_t front = q.front();
                q.pop();
                for (size_t i = 0; i < _vertexs.size(); i++)
                {
                    if (visited[i] == false && _matrix[front][i] != MAX_W)
                    {
                        printf("[%d:%s]", i, _vertexs[i].c_str());
                        visited[i] = true;
                        q.push(i);
                    }
                }
            }
 
            cout << endl;
            dSize = q.size();
            ++d;
        }
        cout << endl;
    }
 
private:
    //将传入我V 类型（本例是string)和对应的索引编号对应上。
    map<V, size_t> _vIndexMap;
    vector<V> _vertexs;        //顶点集合
    vector<vector<W>> _matrix; //存储边集合的矩阵
};
 
int main()
{
 
    // Graph<char, int, INT_MAX, true> g("01234", 4);
    // g.AddEdge('0', '1', 1);
    // g.AddEdge('0', '3', 4);
    // g.AddEdge('1', '3', 2);
    // g.AddEdge('1', '2', 9);
    // g.AddEdge('2', '3', 8);
    // g.AddEdge('2', '1', 5);
    // g.AddEdge('2', '0', 3);
    // g.AddEdge('3', '2', 6);
    // g.Print();
    // cout << g.GetVertexIndex('2') << endl;
 
    string a[] = {"zhangsan", "lisi", "wangwu", "zhaoliu", "zhouqi"};
    Graph<string, int> g1(a, sizeof(a) / sizeof(string));
    g1.AddEdge("zhangsan", "lisi", 100);
    g1.AddEdge("zhangsan", "wangwu", 200);
    g1.AddEdge("wangwu", "zhaoliu", 30);
    g1.AddEdge("wangwu", "zhouqi", 30);
 
    g1.Bfs("zhangsan");
 
    system("pause");
    return 0;
}